#leetcode题目12：整数转罗马数字
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：模拟

class Solution:
    def intToRoman(self, num: int) -> str:

        values=[1000,900,500,400,100,90,50,40,10,9,5,4,1]
        numerals=["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        res=""
        for i in range(len(values)):
            while num>=values[i]:
                num-=values[i]
                res+=numerals[i]
        return res



#测试数据
num=3
#预期输出：III
solution=Solution()
print(solution.intToRoman(num))

num=4
#预期输出：IV
solution=Solution()
print(solution.intToRoman(num))

num=9
#预期输出：IX
solution=Solution()
print(solution.intToRoman(num)) 

num=58
#预期输出：LVIII
solution=Solution()
print(solution.intToRoman(num))

num=1994
#预期输出：MCMXCIV
solution=Solution()
print(solution.intToRoman(num))

